package leetcode11_20;

import org.junit.Test;

import java.util.Arrays;

/**
 * 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。
 * 返回这三个数的和。假定每组输入只存在唯一答案。
 * @author shhjiang_001
 * @create 2020-03-11 0:25
 */
public class Solution16 {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int res = nums[0]+ nums[1]+ nums[2];
        int m = res;
        for(int i = 0 ; i < nums.length-2 ; i++){
            int le = i+1,ri = nums.length-1;
            while(le < ri){
                int ans = nums[i]+ nums[le]+ nums[ri]-target;
                if(ans > 0){
                    ri--;
                    if((le < ri)&&(nums[i]+ nums[le]+ nums[ri]-target < 0)){
                        m = ans;
                        int n = (nums[i]+ nums[le]+ nums[ri]-target)*-1;
                        m = (m>n)? (nums[i]+ nums[le]+ nums[ri]):(nums[i]+ nums[le]+ nums[ri+1]);

                    }else {
                        m = nums[i]+ nums[le]+ nums[ri+1];
                    }
                }else if(ans < 0){
                    le++;
                    if((le < ri)&&nums[i]+ nums[le]+ nums[ri]-target > 0){
                        m = ans*-1;
                        int n = nums[i]+ nums[le]+ nums[ri]-target;
                        m = (m>n)? (nums[i]+ nums[le]+ nums[ri]):(nums[i]+ nums[le-1]+ nums[ri]);

                    }else {
                        m = nums[i]+ nums[le-1]+ nums[ri];
                    }
                }else{
                    return target;
                }
                res = (Math.abs(res-target)>Math.abs(m -target))? m:res;
            }
        }
        return res;
    }
    @Test
    public void test() {
        Solution16 solution16 = new Solution16();
        int i = solution16.threeSumClosest(new int[]{-1, -5,-3,-4,2,-2}, 0);
        System.out.println(i);
    }

}
